
public class TreeImplwork implements Tree{
	
	private Node root=null;
	
	private int hoehe=0;
	private int anzKnoten=0;
	private double pfadlaenge = 0;
	
//-------------------------- Oeffentliche Methoden -----------------------------------------
	
	/**
	 * Element einf�gen
	 * @param e einzuf�gendes Element
	 *  @return true: Element eingef�gt
	 */
	public boolean insert(Element e)
	{
		root = insertTree(root,e);
		return true;
		
	}
	
	/**
	 * Element suchen
	 * @param id Schl�ssel des zu suchenden Elementes
	 *  @return gesuchtes Element; null : Element nicht gefunden
	 */
	public Element search(int id)
	{
		Element e = search(root, id);
		return e;
		
	}
	
	/**
	 * Element suchen (nicht rekursive Variante)
	 * @param id Schl�ssel des zu suchenden Elementes
	 *  @return gesuchtes Element; null : Element nicht gefunden
	 */
	public Element search2(int id)
	{
		Element e = search2(root, id);
		return e;
		
	}
	
	/**
	 * Element l�schen 
	 * @param id Schl�ssel des zu l�schenden Elementes
	 */
	public void delete(int id)
	{
		root = delete(root,id);
	}
	
	/**
	 * Baum ausgeben (Inorder 
	 */
	public void show()
	{
		showInorder(root);
	}
	
	/**
	 * H�he des Baums bestimmen
	 * @return H�he des Baumes
	 */
	public int height()
	{
		hoehe = 0;
		height(root,0);
		return hoehe;
	}
	
	/**
	 * Durchschnittliche Pfadl�nge des Baums bestimmen
	 * @return Durchschnittliche Pfadl�nge
	 */
	public double length()
	{
		pfadlaenge = 0;
		anzKnoten = 0;
		length(root, 0);
		return (pfadlaenge/anzKnoten);
	}
	
	
//-------------------------- Private Methoden -----------------------------------------
	
	private void showInorder(Node r)
	{
		if(r != null) {
			showInorder(r.getLeft());
			System.out.println(r.getItem().getId());
			showInorder(r.getRight());
		}
	}
	
	private Element search(Node r, int id)
	{
		if(r == null)
			return null;
		if(id == r.getItem().getId())
			return r.getItem();
		if(r.getItem().getId() > id)
			return(search(r.getLeft(), id));
		else
			return(search(r.getRight(), id));
	}
	
	/**
	 * nicht rekursive Variante von search
	*/
	private Element search2(Node root, int id)
	{
		Node test = root;
		while(true) {
			if(test == null)
				return null;
			if(test.getItem().getId() > id) {
				test = test.getLeft();
			} else if(test.getItem().getId() < id) {
				test = test.getRight();
			} else
				return test.getItem();
		}
	}
	
	public Node delete(Node root, int id)
	{
		Node test;
		if(root == null)
			return null;
		if(id == root.getItem().getId()) {
			if(root.getLeft() == null && root.getRight() == null)
				return null;
			if(root.getLeft() == null && root.getRight() != null)
				return root.getRight();
			if(root.getLeft() != null && root.getRight() == null)
				return root.getLeft();
			if(root.getLeft() != null && root.getRight() != null) {
				test = root.getLeft();
				while(test.getRight() != null)
					test = test.getRight();
				if(test != root.getLeft())
					test.setLeft(root.getLeft());
				test.setRight(root.getRight());
				root = null;
				return test;
			}
		}
		if(root.getItem().getId() > id)
			root.setLeft(delete(root.getLeft(), id));
		if(root.getItem().getId() < id)
			root.setRight(delete(root.getRight(), id));
		return root;
	}
	
	private Node insertTree(Node root, Element e)
	{
		Node neu;
		if(root == null) {
			neu = new Node();
			neu.setItem(e);
			neu.setLeft(null);
			neu.setRight(null);
			root = neu;
		}
		if(e.getId() < root.getItem().getId())
			root.setLeft(insertTree(root.getLeft(), e));
		if(e.getId() > root.getItem().getId())
			root.setRight(insertTree(root.getRight(), e));
		return root;
	}
	

	private void height(Node root, int h)
	{
		if (root!=null)
		{
			h++;
			if (h > hoehe)
				hoehe = h;
			height(root.getLeft(),h);
			height(root.getRight(),h);
		}
	}
	
	private void length(Node root, int h)
	{
		if (root!=null)
		{
			h++;
			pfadlaenge += h;
			anzKnoten++;
			length(root.getLeft(),h);
			length(root.getRight(),h);
		}
	}
}
